#pragma once

#include <memory>
#include <functional>
#include <iostream>
#include <list>
#include <vector>

using namespace std;

#define LEFT_CHILD 1
#define RIGHT_CHILD 2
#define DATA 3

//#define BST_TREE_DEBUG 1

template <class T, class Alloc = allocator<T>, class CompareFunction = less<T>>
class LeBST
{
private:
	Alloc alloc;
	extern struct LeBSTModifi;

	struct LeBSTNode
	{
		T *data;
		shared_ptr<LeBSTNode> left, right; // original left & right children

		shared_ptr<LeBSTModifi> mod;
		
		T * getData(int v) // version
		{
			if (mod != NULL && mod->version <= v && mod->field == DATA) 
				return mod->data;
			else
				return data;
		}

		shared_ptr<LeBSTNode> getLeft(int v) // version
		{
			if (mod != NULL && mod->version <= v && mod->field == LEFT_CHILD)
				return mod->pointer;
			else 
				return left;
		}

		shared_ptr<LeBSTNode> getRight(int v) // version
		{
			if (mod != NULL && mod->version <= v && mod->field == RIGHT_CHILD)
				return mod->pointer;
			else 
				return right;
		}

		LeBSTNode(T * x) : data(x), left(NULL), right(NULL), mod(NULL) {}
		
		LeBSTNode(LeBSTNode const &) { throw logic_error( "can't copy LeBSTNode" ); }

		~LeBSTNode() 
		{
#ifdef BST_TREE_DEBUG
			cout << "deleting LeBSTNode: data=" << data << "; left=" << left << "; right=" << right << "; mod=" << mod << endl; 
#endif

			Alloc alloc;
			alloc.destroy(data);
			alloc.deallocate(data, 1);
		}
	};
	
	struct LeBSTModifi
	{
		int version; // version number in which the node was modified (NULL if wasn't)
		int field; // LEFT_CHILD or RIGHT_CHILD or DATA (or NULL if node not modified)
		shared_ptr<LeBSTNode> pointer; // pointer to the new element (can be NULL after modification)
		T *data; // new data only for field == DATA

		LeBSTModifi() : version(0), field(NULL), pointer(NULL), data(0) {}

		~LeBSTModifi() 
		{
#ifdef BST_TREE_DEBUG
			cout << "deleting LeBSTModifi: version=" << version << "; field=" << field << "; ptr=" << pointer << "; data=" << data << endl; 
#endif
			Alloc alloc;
			alloc.destroy(data);
			alloc.deallocate(data, 1);
		}
	};

	struct LeBSTRoot
	{
		int fromVersion; // version number in which this trunk was created
		shared_ptr<LeBSTNode> node; // pointer to the tree nodes

		LeBSTRoot() : fromVersion(0), node(NULL) {}

		~LeBSTRoot()
		{ 
#ifdef BST_TREE_DEBUG
			cout << "deleting LeBSTRoot: fromVersion=" << fromVersion << "; node=" << node << endl;
#endif
		}
	};

	struct Result
	{
		shared_ptr<LeBSTNode> returned;
		bool hasValue; // to mark that NULL is a return value (in case returned == NULL).

		Result(shared_ptr<LeBSTNode> r, bool nn) : returned(r), hasValue(nn) {}
	};

public:

	LeBST(CompareFunction cmprr) : comparer(cmprr) : this() {}
	
	LeBST() : version(0) {}

	~LeBST()
	{
#ifdef BST_TREE_DEBUG
		cout << "deleting LeBST." << endl;
#endif
	}

	int getVersionNumber() { return version; }

	// assume the newest version if not specified
	bool find(T x) { return find(x, version); }

	// find within the tree of version 'v'
	bool find(T x, int v) { return findNode(&x, v) != NULL; }

	// always insert to the newest version
	

	bool insert(T &x)
	{
		T *ptr = alloc.allocate(1,0);
		alloc.construct(ptr, x);

		if (roots.size() == 0) // adding first element into the tree
		{
			shared_ptr<LeBSTRoot> root = shared_ptr<LeBSTRoot>(new LeBSTRoot());
			root->fromVersion = ++version;
			root->node = shared_ptr<LeBSTNode>(new LeBSTNode(ptr));
			roots.push_back(*root);
			return true;
		}

		LeBSTNode * found = findNode(&*ptr, version);
		if (found != NULL)
		{
			alloc.destroy(ptr);
			alloc.deallocate(ptr, 1);
			return false;
		}
		
		shared_ptr<LeBSTNode> returned = insertNode(&*ptr, roots.back().node);
		if (returned != NULL)
		{
			// add new root
			shared_ptr<LeBSTRoot> root = shared_ptr<LeBSTRoot>(new LeBSTRoot());
			root->fromVersion = version;
			root->node = returned;
			roots.push_back(*root);
		}
		return true; //whatever ?
	}

	bool insert(T &&x)
	{
		return insert(x);
	}

	bool erase(T x)
	{ 
		if (roots.size() == 0) return false;

		LeBSTNode * found = findNode(&x, version);
		if (found == NULL)
			return false;

		Result * returned = eraseNode(&x, roots.back().node);
		if (returned->hasValue)
		{
			// add new root
			shared_ptr<LeBSTRoot> root = shared_ptr<LeBSTRoot>(new LeBSTRoot());
			root->fromVersion = version;
			root->node = returned->returned;
			roots.push_back(*root);
		}
		delete returned;
		return true; // whatever ?
	}

	//T & min() { return (min(&*root))->data; }

	//T & max() { return (max(&*root))->data; }

private:
	int version; // global current version
	CompareFunction comparer;	

	list<LeBSTRoot> roots; // list of roots

	LeBSTRoot * findRootForVersion(int v)
	{
		if (roots.size() != 0)
		{
			list<LeBSTRoot>::iterator i = roots.end();
			do 
			{
				// iterate roots back to front looking for the first root
				// created with version <= to the given version
				if ((*--i).fromVersion <= v)
					return &(*i);
			} while (i != roots.begin());
		}
		return NULL;
	}

	LeBSTNode * findNode(T *x, int version)
	{
		// start with finding an apropriate root for the given version
		LeBSTRoot * root = findRootForVersion(version);
		if (root != NULL)
		{
			LeBSTNode * node = &*(root->node);
			while (true)
			{
				if (node == NULL)
					return NULL; // not found
				else if (comparer(*x, *node->getData(version)))
					node = &(*node->getLeft(version)); // go left
				else if (comparer(*node->getData(version), *x))
					node = &(*node->getRight(version)); // go right
				else
					return node; // found
			}
		}
		return NULL;
	}

	// beware. a recurrent function
	shared_ptr<LeBSTNode> insertNode(T *x, shared_ptr<LeBSTNode> node)
	{
		if (node == NULL)
		{
			++version;
			return shared_ptr<LeBSTNode>(new LeBSTNode(x));// create leaf
		}
		if (comparer(*x, *node->getData(version)))
		{ // go left
			if (node->mod != NULL)
			{ // inspected node was modified
				if ((node->mod->field == LEFT_CHILD && node->mod->pointer == NULL)
					|| (node->mod->field == RIGHT_CHILD && node->left == NULL))
				{ // nowhere to follow, this is the place to insert
					T *ptr = alloc.allocate(1,0);
					alloc.construct(ptr, *node->data);
					// replace 'node' with new one, and return it
					LeBSTNode * newLeaf = new LeBSTNode(x); // create leaf
					//TODO
					LeBSTNode * newNode = new LeBSTNode(ptr); // and current node new substitute
					newNode->left = shared_ptr<LeBSTNode>(newLeaf); // link leaf
					newNode->right = node->mod->pointer;
					++version;
					return shared_ptr<LeBSTNode>(newNode); // propagate it up
				}
				else
				{
					shared_ptr<LeBSTNode> returned;
					// if node's left child was modified, and it is not NULL, follow modifi pointer
					if (node->mod->field == LEFT_CHILD && node->mod->pointer != NULL)
						returned = insertNode(x, node->mod->pointer); // go deeper recursively
					else // right was modified, but can follow left
						returned = insertNode(x, node->left); // go deeper recursively

					if (returned != NULL)
					{ // go up one more level
						T *ptr = alloc.allocate(1,0);
						alloc.construct(ptr, *node->data);
						// replace 'node' with new one, rebind its hanging tentacles and return it
						LeBSTNode * newNode = new LeBSTNode(ptr);
						newNode->left = returned;
						newNode->right = node->right;
						return shared_ptr<LeBSTNode>(newNode); // propagate it up
					}
					return shared_ptr<LeBSTNode>(NULL);
				}
			}
			else if (node->left != NULL)
			{ // node wasn't modified
				shared_ptr<LeBSTNode> returned = insertNode(x, node->left); // go deeper recursively
				if (returned != NULL)
				{
					node->mod = shared_ptr<LeBSTModifi>(new LeBSTModifi());
					// simply use modifi fields in 'node'
					node->mod->version = version;
					node->mod->field = LEFT_CHILD;
					node->mod->pointer = returned;
				}
				return shared_ptr<LeBSTNode>(NULL); // no need to propagate up, as the modifi fields were used
			}
			else
			{ // left node is empty
				// create new node, and attach it as the 'modified pointer'
				node->mod = shared_ptr<LeBSTModifi>(new LeBSTModifi());
				LeBSTNode * newLeaf = new LeBSTNode(x);
				node->mod->version = ++version;
				node->mod->field = LEFT_CHILD;
				node->mod->pointer = shared_ptr<LeBSTNode>(newLeaf);
				return shared_ptr<LeBSTNode>(NULL);
			}
		}
		else if (comparer(*node->getData(version), *x)) 
		{ // go right
			if (node->mod != NULL)
			{ // inspected node was modified
				if ((node->mod->field == RIGHT_CHILD && node->mod->pointer == NULL)
					|| (node->mod->field == LEFT_CHILD && node->right == NULL))
				{ // nowhere to follow, this is the place to insert
					T *ptr = alloc.allocate(1,0);
					alloc.construct(ptr, *node->data);
					// replace 'node' with new one, and return it
					LeBSTNode * newLeaf = new LeBSTNode(x); // create leaf
					LeBSTNode * newNode = new LeBSTNode(ptr); // and current node new substitute
					newNode->right = shared_ptr<LeBSTNode>(newLeaf); // link leaf
					newNode->left = node->mod->pointer;
					++version;
					return shared_ptr<LeBSTNode>(newNode); // propagate it up
				}
				else
				{
					shared_ptr<LeBSTNode> returned;
					// if node's right child was modified, and it is not NULL, follow modifi pointer
					if (node->mod->field == RIGHT_CHILD && node->mod->pointer != NULL)
						returned = insertNode(x, node->mod->pointer); // go deeper recursively
					else // left was modified, but can follow right
						returned = insertNode(x, node->right); // go deeper recursively

					if (returned != NULL)
					{ // go up one more level
						T *ptr = alloc.allocate(1,0);
						alloc.construct(ptr, *node->data);
						// replace 'node' with new one, rebind its hanging tentacles and return it
						LeBSTNode * newNode = new LeBSTNode(ptr);
						newNode->right = returned;
						newNode->left = node->left;
						return shared_ptr<LeBSTNode>(newNode); // propagate it up
					}
					return shared_ptr<LeBSTNode>(NULL);
				}
			}
			else if (node->right != NULL)
			{ // node wasn't modified
				shared_ptr<LeBSTNode> returned = insertNode(x, node->right); // go deeper recursively
				if (returned != NULL)
				{
					node->mod = shared_ptr<LeBSTModifi>(new LeBSTModifi());
					// simply use modifi fields in 'node'
					node->mod->version = version;
					node->mod->field = RIGHT_CHILD;
					node->mod->pointer = returned;
				}
				return shared_ptr<LeBSTNode>(NULL); // no need to propagate up, as the modifi fields were used
			}
			else
			{ // right node is empty
				// create new node, and attach it as the 'modified pointer'
				node->mod = shared_ptr<LeBSTModifi>(new LeBSTModifi());
				node->mod->version = ++version;
				node->mod->field = RIGHT_CHILD;
				node->mod->pointer = shared_ptr<LeBSTNode>(new LeBSTNode(x));
				return shared_ptr<LeBSTNode>(NULL);
			}
		}
		else return shared_ptr<LeBSTNode>(NULL); // item already exists. allow no duplicates.
	}

	Result * eraseNode(T *x, shared_ptr<LeBSTNode> node)
	{
		if (node == NULL)
			return new Result(NULL, false);
		if (comparer(*x, *node->getData(version)))
		{ // go left
			if (node->mod != NULL)
			{ // inspected node was modified
				if ((node->mod->field == LEFT_CHILD && node->mod->pointer == NULL)
					|| (node->mod->field == RIGHT_CHILD && node->left == NULL))
				{ // not found
					return new Result(NULL, false);
				}
				else
				{
					Result * returned = NULL;
					// if node's left child was modified, and it is not NULL, follow modifi pointer
					if (node->mod->field == LEFT_CHILD && node->mod->pointer != NULL)
						returned = eraseNode(x, node->mod->pointer); // go deeper recursively
					else // right was modified, but can follow left
						returned = eraseNode(x, node->left); // go deeper recursively

					if (returned->hasValue)
					{ // go up one more level
						T *ptr = alloc.allocate(1,0);
						alloc.construct(ptr, *node->data);
						// replace 'node' with new one, rebind its hanging tentacles and return it
						shared_ptr<LeBSTNode> newNode = shared_ptr<LeBSTNode>(new LeBSTNode(ptr));
						newNode->left = returned->returned;
						newNode->right = node->right;
						delete returned;
						return new Result(newNode, true); // propagate it up
					}
					delete returned;
					return new Result(NULL, false);
				}
			}
			else if (node->left != NULL)
			{ // node wasn't modified
				Result * returned = eraseNode(x, node->left); // go deeper recursively
				if (returned->hasValue)
				{
					node->mod = shared_ptr<LeBSTModifi>(new LeBSTModifi());
					// simply use modifi fields in 'node'
					node->mod->version = version;
					node->mod->field = LEFT_CHILD;
					node->mod->pointer = returned->returned;
				}
				delete returned;
				return new Result(NULL, false); // no need to propagate up, as the modifi fields were used
			}
			else
			{ // left node is empty
				return new Result(NULL, false);
			}
		}
		else if (comparer(*node->getData(version), *x)) 
		{ // go right
			if (node->mod != NULL)
			{ // inspected node was modified
				if ((node->mod->field == RIGHT_CHILD && node->mod->pointer == NULL)
					|| (node->mod->field == LEFT_CHILD && node->right == NULL))
				{ // not found
					return new Result(NULL, false);
				}
				else
				{
					Result * returned = NULL;
					// if node's right child was modified, and it is not NULL, follow modifi pointer
					if (node->mod->field == RIGHT_CHILD && node->mod->pointer != NULL)
						returned = eraseNode(x, node->mod->pointer); // go deeper recursively
					else // left was modified, but can follow right
						returned = eraseNode(x, node->right); // go deeper recursively

					if (returned->hasValue)
					{ // go up one more level
						T *ptr = alloc.allocate(1,0);
						alloc.construct(ptr, *node->data);
						// replace 'node' with new one, rebind its hanging tentacles and return it
						shared_ptr<LeBSTNode> newNode = shared_ptr<LeBSTNode>(new LeBSTNode(ptr));
						newNode->right = returned->returned;
						newNode->left = node->left;
						delete returned;
						return new Result(newNode, true); // propagate it up
					}
					delete returned;
					return new Result(NULL, false);
				}
			}
			else if (node->right != NULL)
			{ // node wasn't modified
				Result * returned = eraseNode(x, node->right); // go deeper recursively
				if (returned->hasValue)
				{
					node->mod = shared_ptr<LeBSTModifi>(new LeBSTModifi());
					// simply use modifi fields in 'node'
					node->mod->version = version;
					node->mod->field = RIGHT_CHILD;
					node->mod->pointer = returned->returned;
				}
				delete returned;
				return new Result(NULL, false); // no need to propagate up, as the modifi fields were used
			}
			else
			{ // right node is empty
				return new Result(NULL, false);
			}
		}
		else
		{
			if (node->getRight(version) != NULL)
			{
				shared_ptr<LeBSTNode> succ = successorShallow(node, version);
				Result * returned = deleteMin(node->getRight(version));
				if (returned->hasValue)
				{ 
					T *ptr = alloc.allocate(1,0);
					alloc.construct(ptr, *succ->getData(version));

					shared_ptr<LeBSTNode> newNode = shared_ptr<LeBSTNode>(new LeBSTNode(ptr)); // and current node new substitute
					newNode->left = node->getLeft(version);
					newNode->right = returned->returned;
					delete returned;
					return new Result(newNode, true); // propagate it up
				}
				else
				{
					delete returned;
					if (node->mod != NULL)
					{
						T *ptr = alloc.allocate(1,0);
						alloc.construct(ptr, *succ->getData(version));

						shared_ptr<LeBSTNode> newNode = shared_ptr<LeBSTNode>(new LeBSTNode(ptr));
						newNode->left = node->getLeft(version);
						newNode->right = node->getRight(version);
						return new Result(newNode, true); // propagate it up
					}
					else
					{
						node->mod = shared_ptr<LeBSTModifi>(new LeBSTModifi());
						node->mod->field = DATA;
						node->mod->version = version;

						T *ptr = alloc.allocate(1,0);
						alloc.construct(ptr, *succ->getData(version));

						node->mod->data = ptr;
						return new Result(NULL, false);
					}
				}
			}
			else return new Result(node->getLeft(version++), true); // succ == NULL
		}
	}

	Result * deleteMin(shared_ptr<LeBSTNode> node)
	{
		if (node->getLeft(version) != NULL)
		{
			Result * returned = deleteMin(node->getLeft(version));
			if (returned->hasValue)
			{ // go up one more level
				T *ptr = alloc.allocate(1,0);
				alloc.construct(ptr, *node->data);
				// replace 'node' with new one, rebind its hanging tentacles and return it
				shared_ptr<LeBSTNode> newNode = shared_ptr<LeBSTNode>(new LeBSTNode(ptr));
				newNode->left = returned->returned;
				newNode->right = node->right;
				delete returned;
				return new Result(newNode, true); // propagate it up
			}
			delete returned;
			return new Result(NULL, false);
		}
		else return new Result(node->getRight(version++), true);
	}

	shared_ptr<LeBSTNode> successorShallow(shared_ptr<LeBSTNode> from, int v)
	{
		shared_ptr<LeBSTNode> temp = from->getRight(v);
		if (temp != NULL) temp = min(temp, v);
		return temp;
	}

	shared_ptr<LeBSTNode> predecessorShallow(shared_ptr<LeBSTNode> from, int v)
	{
		shared_ptr<LeBSTNode> temp = from->getLeft(v);
		if (temp != NULL) temp = max(temp, v);
		return temp;
	}

	shared_ptr<LeBSTNode> min(shared_ptr<LeBSTNode> from, int v)
	{
		shared_ptr<LeBSTNode> node = from;
		while (node->getLeft(v) != NULL) node = node->getLeft(v);
		return node;
	}

	shared_ptr<LeBSTNode> max(shared_ptr<LeBSTNode> from, int v)
	{
		shared_ptr<LeBSTNode> node = from;
		while (node->getRight(v) != NULL) node = node->getRight(v);
		return node;
	}

	Result * successor(shared_ptr<LeBSTNode> node, T *x, int v)
	{
		if (node == NULL)
			return NULL;
		else if (comparer(*x, *node->getData(v)))
		{
			Result * returned = successor(node->getLeft(v), x, v); // go left
			if (returned->hasValue)
				return returned;

			delete returned;

			return new Result(node, true);
		}
		else if (comparer(*node->getData(v), *x))
			return successor(node->getRight(v), x, v); // go right
		else
		{
			if (node->getRight(v) != NULL)
				return new Result(successorShallow(node, v), true);
			else
				return new Result(NULL, false);
		}
		return NULL;
	}

	Result * predecessor(shared_ptr<LeBSTNode> node, T *x, int v)
	{
		if (node == NULL)
			return NULL;
		else if (comparer(*x, *node->getData(v)))
			return predecessor(node->getLeft(v), x, v); // go left
		else if (comparer(*node->getData(v), *x))
		{
			Result * returned = predecessor(node->getRight(v), x, v); // go right
			if (returned->hasValue)
				return returned;
			
			delete returned;
			
			return new Result(node, true);
		}
		else
		{
			if (*node->getLeft(v) != NULL)
				return new Result(predecessorShallow(node, v), true);
			else
				return new Result(NULL, false);
		}
		return NULL;
	}

public:
	class iterator
	{
		friend class LeBST;
	private:
		int iversion;
		LeBST<T> * tree;
		T * value;
	public:
		iterator(LeBST<T> * t) : tree(t), iversion(0), value(NULL) {}
		iterator(LeBST<T> * t, int v, T * val) : tree(t), iversion(v), value(val) {}

		bool operator==(const iterator& other) const
		{	// test for iterator equality
			return (tree == NULL || tree != other.tree) ? false : (value == other.value);
		}

		bool operator!=(const iterator& other) const
		{	// test for iterator equality
			return !((tree == NULL || tree != other.tree) ? false : (value == other.value));
		}

		T operator*() const
		{	// return designated value
			return *value;
		}

		//T operator->() const
		//{	// return pointer to class object
		//	return (&**this);
		//}

		iterator & operator++()
		{ // pre increment
			if (tree != NULL && value != NULL)
			{
				LeBSTRoot * root = tree->findRootForVersion(iversion);
				if (root != NULL)
				{
					if (root->node != NULL)
					{
						Result * result = tree->successor(root->node, value, iversion);
						if (result->hasValue && result->returned != NULL)
						{
							value = result->returned->getData(iversion);
							delete result;
							return *this;
						}
						delete result;
					}
				}
			}
			value = NULL;
			return *this;
		}

		iterator & operator++(int)
		{ // post increment
			if (tree != NULL && value != NULL)
			{
				LeBSTRoot * root = tree->findRootForVersion(iversion);
				if (root != NULL)
				{
					if (root->node != NULL)
					{
						Result * result = tree->successor(root->node, value, iversion);
						if (result->hasValue && result->returned != NULL)
						{
							T * oldValue = value;
							value = result->returned->getData(iversion);
							delete result;
							return iterator(tree, iversion, oldValue);
						}
						delete result;
					}
				}
			}
			value = NULL;
			return *this;
		}
	};

	iterator begin() { return begin(version); }

	iterator begin(int v)
	{
		LeBSTRoot * root = findRootForVersion(v);
		if (root != NULL)
		{
			shared_ptr<LeBSTNode> node = root->node;
			if (node != NULL)
			{
				shared_ptr<LeBSTNode> found = min(node, v);
				if (found != NULL) return iterator(this, v, found->getData(v));
			}
		}
		return iterator(this);
	}

	iterator end() { return end(version); }

	iterator end(int v) { return iterator(this); }
};